# 剑指 Offer 29. 顺时针打印矩阵

# 一、题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出:[1,2,3,6,9,8,7,4,5]

示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出:[1,2,3,4,8,12,11,10,9,5,6,7]

限制:

  • 0 <= matrix.length <= 100
  • 0 <= matrix[i].length <= 100

# 二、题目解析

对于一个二维矩阵来说,它包含了如下的边界与打印顺序:

  • 1、顶层,我们可以定义为 top,在顶层是按照从左到右的顺序进行打印
  • 2、右列,我们可以定义为 right,在右列是按照从上到小的顺序进行打印
  • 3、底层,我们可以定义为 bottom,在顶层是按照从右到左的顺序进行打印
  • 2、左列,我们可以定义为 left,在左列是按照从下到上的顺序进行打印

img

在打印的过程中,矩阵的可打印区间在不断的发生变化:

  • 每当把从左到右把一行打印完毕之后,整个矩阵就在顶部少了一层,即 top 位置向下挪了一层
  • 每当把从上到下把一列打印完毕之后,整个矩阵就在右部少了一列,即 right 位置向左挪了一列
  • 每当把从右到左把一行打印完毕之后,整个矩阵就在底部少了一层,即 bottom 位置向上挪了一层
  • 每当把从下到上把一列打印完毕之后,整个矩阵就在左部少了一列,即 left 位置向右挪了一列

每当 top、right、bottom、left 发生挪到之后,需要判断它们挪动之后的区间是否还存在。

  • 1、如果还存在,那么就继续按照 top、right、bottom、left 的顺序进行打印
  • 2、如果不存在了,那么说明矩阵中的所有元素打印完毕

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        
        // 特殊情况,边界处理,比如 matrix = [],无法获取  matrix[0]
        if (matrix.length == 0) {
            return new int[0];
        }

        // 设置一个一维数组 res 用来记录二维数组 matrix 中的顺时针打印的结果
        int[] res = new int[matrix.length * matrix[0].length];

        // 在打印的过程中,不断的缩小着打印的区间
        // 每当把从左到右把一行打印完毕之后,整个矩阵就在顶部少了一层,后续打印不需要再去处理它们
        // 每当把从上到下把一列打印完毕之后,整个矩阵就在右部少了一列,后续打印不需要再去处理它们
        // 每当把从右到左把一行打印完毕之后,整个矩阵就在底部少了一层,后续打印不需要再去处理它们
        // 每当把从下到上把一列打印完毕之后,整个矩阵就在左部少了一列,后续打印不需要再去处理它们
        // 因此,设置四个变量,用来记录打印的区间变化

        // top 表示顶部所在的层数位置,一开始在第 0 层
        int top = 0 ;

        // bottom 表示底部所在的层数位置,一开始在第 matrix.length - 1 层
        int bottom = matrix.length - 1 ;

        // left 表示左部所在的列数位置,一开始在第 0 列
        int left = 0 ; 

        // right 表示右部所在的列数位置,一开始在第 matrix[0].length - 1 列
        int right = matrix[0].length - 1;

        // 顺时针打印矩阵过程中,填充 res 数组,从索引位置 0 的地方开始填充
        int index = 0;

        // 使用一个 while 循环进行打印,只要打印区间中还有值就一直打印
        // 直到出现边界越界,即打印区间不存在元素了,跳出循环
        while (true) {

            // 1、从左到右,打印这一行
            // 此时,边界从 left 到 right
            for (int i = left; i <= right; i++) {

                // 将当前元素填充到 res 中
                // 此时,一直都是在 top 这一层
                res[index] = matrix[top][i];

                // index 的元素填充完毕之后,开始填充下一个元素
                index++;

            }

            // 经过上面这个循环之后,此时,顶部这一层的所有元素已经打印完毕
            // 整个打印区间需要删除这一行了,因此,将 top 的层数向下挪
            top += 1;

            // 如果此时发现顶部位置越过了底部位置,说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( top > bottom ) {
                break;
            }

            // 2、从上到下,打印这一列
            // 此时,边界从 top 到 bottom
            for (int i = top; i <= bottom; i++) {

                // 将当前元素填充到 res 中
                // 此时,一直都是在 right 这一列
                res[index] = matrix[i][right];

                // index 的元素填充完毕之后,开始填充下一个元素
                index++;

            }

            // 经过上面这个循环之后,此时,右部这一列的所有元素已经打印完毕
            // 整个打印区间需要删除这一列了,因此,将 right 的层数向左挪
            right -= 1;

            // 如果此时发现右部位置越过了左部位置,说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( right < left ) {
                break;
            }

            // 3、从右到左,打印这一行
            // 此时,边界从 right 到 left
            for (int i = right; i >= left; i--) {

                // 将当前元素填充到 res 中
                // 此时,一直都是在 bottom 这一层
                res[index] = matrix[bottom][i];

                // index 的元素填充完毕之后,开始填充下一个元素
                index++;

            }

            // 经过上面这个循环之后,此时,底部这一层的所有元素已经打印完毕
            // 整个打印区间需要删除这一行了,因此,将 bottom 的层数向上挪
            bottom -= 1;

            // 如果此时发现顶部位置越过了底部位置,说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( bottom < top ) {
                break;
            }

            // 4、从下到上,打印这一列
            // 此时,边界从 bottom 到 top
            for (int i = bottom; i >= top; i--) {

                // 将当前元素填充到 res 中
                // 此时,一直都是在 left 这一列
                res[index] = matrix[i][left];

                // index 的元素填充完毕之后,开始填充下一个元素
                index++;
            }

            // 经过上面这个循环之后,此时,左部这一列的所有元素已经打印完毕
            // 整个打印区间需要删除这一列了,因此,将 left 的层数向右挪
            left += 1;

            // 如果此时发现右部位置越过了左部位置,说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( left > right ) {
                break;
            }

        }

        // 最后,返回结果即可
        return res;
    }
}

# **2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {

        // 特殊情况,边界处理,比如 matrix = [],无法获取  matrix[0]
        if (matrix.size() == 0) {
            return {};
        }

        // 设置一个一维数组 res 用来记录二维数组 matrix 中的顺时针打印的结果

        vector<int> res(matrix.size() * matrix[0].size());

        // 在打印的过程中,不断的缩小着打印的区间
        // 每当把从左到右把一行打印完毕之后,整个矩阵就在顶部少了一层,后续打印不需要再去处理它们
        // 每当把从上到下把一列打印完毕之后,整个矩阵就在右部少了一列,后续打印不需要再去处理它们
        // 每当把从右到左把一行打印完毕之后,整个矩阵就在底部少了一层,后续打印不需要再去处理它们
        // 每当把从下到上把一列打印完毕之后,整个矩阵就在左部少了一列,后续打印不需要再去处理它们
        // 因此,设置四个变量,用来记录打印的区间变化

        // top 表示顶部所在的层数位置,一开始在第 0 层
        int top = 0 ;

        // bottom 表示底部所在的层数位置,一开始在第 matrix.length - 1 层
        int bottom = matrix.size() - 1 ;

        // left 表示左部所在的列数位置,一开始在第 0 列
        int left = 0 ; 

        // right 表示右部所在的列数位置,一开始在第 matrix[0].length - 1 列
        int right = matrix[0].size() - 1;

        // 顺时针打印矩阵过程中,填充 res 数组,从索引位置 0 的地方开始填充
        int index = 0;

        // 使用一个 while 循环进行打印,只要打印区间中还有值就一直打印
        // 直到出现边界越界,即打印区间不存在元素了,跳出循环
        while (true) {

            // 1、从左到右,打印这一行
            // 此时,边界从 left 到 right
            for (int i = left; i <= right; i++) {

                // 将当前元素填充到 res 中
                // 此时,一直都是在 top 这一层
                res[index] = matrix[top][i];

                // index 的元素填充完毕之后,开始填充下一个元素
                index++;

            }

            // 经过上面这个循环之后,此时,顶部这一层的所有元素已经打印完毕
            // 整个打印区间需要删除这一行了,因此,将 top 的层数向下挪
            top += 1;

            // 如果此时发现顶部位置越过了底部位置,说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( top > bottom ) {
                break;
            }

            // 2、从上到下,打印这一列
            // 此时,边界从 top 到 bottom
            for (int i = top; i <= bottom; i++) {

                // 将当前元素填充到 res 中
                // 此时,一直都是在 right 这一列
                res[index] = matrix[i][right];

                // index 的元素填充完毕之后,开始填充下一个元素
                index++;

            }

            // 经过上面这个循环之后,此时,右部这一列的所有元素已经打印完毕
            // 整个打印区间需要删除这一列了,因此,将 right 的层数向左挪
            right -= 1;

            // 如果此时发现右部位置越过了左部位置,说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( right < left ) {
                break;
            }

            // 3、从右到左,打印这一行
            // 此时,边界从 right 到 left
            for (int i = right; i >= left; i--) {

                // 将当前元素填充到 res 中
                // 此时,一直都是在 bottom 这一层
                res[index] = matrix[bottom][i];

                // index 的元素填充完毕之后,开始填充下一个元素
                index++;

            }

            // 经过上面这个循环之后,此时,底部这一层的所有元素已经打印完毕
            // 整个打印区间需要删除这一行了,因此,将 bottom 的层数向上挪
            bottom -= 1;

            // 如果此时发现顶部位置越过了底部位置,说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( bottom < top ) {
                break;
            }

            // 4、从下到上,打印这一列
            // 此时,边界从 bottom 到 top
            for (int i = bottom; i >= top; i--) {

                // 将当前元素填充到 res 中
                // 此时,一直都是在 left 这一列
                res[index] = matrix[i][left];

                // index 的元素填充完毕之后,开始填充下一个元素
                index++;
            }

            // 经过上面这个循环之后,此时,左部这一列的所有元素已经打印完毕
            // 整个打印区间需要删除这一列了,因此,将 left 的层数向右挪
            left += 1;

            // 如果此时发现右部位置越过了左部位置,说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( left > right ) {
                break;
            }

        }

        // 最后,返回结果即可
        return res;
    }
};